﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.SortCode
{
    //================================================= 快速排序
    //快速排序采用了一种分治的策略，通常称其为分治法
    //基本思路：
    //         1.先从数列中取出一个数作为基准数
    //         2.分区过程，将比这个数打的数全放到它的右边，小于或等于它的数全放到它的左边
    //         3.再对左右区间重复第二步，直到各区间只有一个数
    class QuickSort
    {
        public void Sort(int[] arr)
        {
            sort2(arr, 0, arr.Length - 1);
        }
        void sort2(int[] arr, int left, int right)
        {
            if(left<right)
            {
                int i = left, j = right, x = arr[left];
                while(i<j)
                {
                    while (i < j && arr[j] >= x)
                        j--;
                    if (i < j)
                        arr[i++] = arr[j];

                    while (i < j && arr[i] < x)
                        i++;
                    if (i < j)
                        arr[j--] = arr[i];
                    
                }
                arr[i] = x;


                Console.WriteLine();
                foreach (int m in arr)
                {
                    Console.Write(m);
                    Console.Write(',');
                }
                Console.Write("i = " + i + ",");
                Console.Write("j = " + j + ",");

                sort2(arr, left, i - 1);
                sort2(arr, i + 1, right);
            }
        }
    }
}
